﻿using System;
using System.Collections.Generic;
using FineCollection.Intf;



namespace FineCollection.Cont
{

    struct LinkedListImp<T>
    {
        #region STATIC SERVICE MEMBERS

        internal static readonly IEqualityComparer<T> equator =
            EqualityComparer<T>.Default;

        #endregion



        #region STATE

        internal Chain<T> first, last;
        internal int count;

        #endregion


        internal void Add(T item)
        {
            int theHashCode = equator.GetHashCode(item);
            Add(item, theHashCode);
        }


        internal void Add(T item, int hashCode)
        {
            Chain<T> newChain = 
                new Chain<T> {prev = null, next = null, 
                              item = item, hashCode = hashCode};
            InsertToEnd(newChain);
        }


        internal void InsertToEnd(Chain<T> newChain)
        {
            if (count == 0)
            {
                newChain.prev = newChain.next = null;
                first = last = newChain;
                count = 1;
            }
            else
            {
                last.next = newChain;
                newChain.prev = last;
                newChain.next = null;
                last = newChain;
                count++;
            }
        }


        internal void InsertAtBegin(Chain<T> newChain)
        {
            if (count == 0)
            {
                newChain.prev = newChain.next = null;
                first = last = newChain;
                count = 1;
            }
            else
            {
                newChain.next = first;
                first.prev = newChain;
                newChain.prev = null;
                first = newChain;
                count++;
            }
        }


        internal void InsertBefore(Chain<T> existentChain, Chain<T> newChain)
        {
            Chain<T> prev = existentChain.prev;
            if (prev == null)
            {
                InsertAtBegin(newChain);
            }
            else
            {
                prev.next = newChain;
                newChain.prev = prev;
                newChain.next = existentChain;
                existentChain.prev = newChain;
                count++;
            }
        }


        internal void InsertAfter(Chain<T> existentChain, Chain<T> newChain)
        {
            Chain<T> next = existentChain.next;
            if (next == null)
            {
                InsertToEnd(newChain);
            }
            else
            {
                existentChain.next = newChain;
                newChain.prev = existentChain;
                newChain.next = next;
                next.prev = newChain;
                count++;
            }
        }


        internal Chain<T> FindFirst(T item)
        {
            int theHashCode = equator.GetHashCode(item);
            for (var chain = first; chain != null; chain = chain.next)
                if (chain.hashCode == theHashCode && equator.Equals(chain.item, item))
                    return chain;

            // not found
            return null;
        }


        internal Chain<T> FindFirst(int hashCode, Predicate<T> predicate)
        {
            for (var chain = first; chain != null; chain = chain.next)
                if (chain.hashCode == hashCode && predicate(chain.item))
                    return chain;

            // not found
            return null;
        }


        internal Chain<T> FindFirst(Predicate<T> predicate)
        {
            for (var chain = first; chain != null; chain = chain.next)
                if (predicate(chain.item))
                    return chain;

            // not found
            return null;
        }


        internal void CheckExistence(T item, out bool found)
        {
            int hc = equator.GetHashCode(item);
            CheckExistence(hc, x => equator.Equals(x, item), out found);
        }



        internal void CheckExistence(int hashCode, 
                                     System.Predicate<T> predicate,
                                     out bool found)
        {
            for (var chain = first; chain != null; chain = chain.next)
                if (chain.hashCode == hashCode && predicate(chain.item))
                {
                    found = true;
                    return;
                }

            // not found
            found = false;
        }


        internal void ReplaceFirst(int hashCode, System.Predicate<T> predicate,
                                   T newItem, out bool found)
        {
            for (var chain = first; chain != null; chain = chain.next)
                if (chain.hashCode == hashCode && predicate(chain.item))
                {
                    chain.item = newItem;
                    found = true;
                    return;
                }

            // not found
            found = false;
        }


        internal T ExcludeFirst()
        {
            var excluding = first;
            if (excluding == null)
                throw new CollectionIsEmptyException();

            if (excluding.next != null)
            {
                this.first = excluding.next;
                excluding.next.prev = null;
                count--;
            }
            else
            {
                this.first = this.last = null;
                count = 0;
            }

            return excluding.item;
        }


        internal T ExcludeLast()
        {
            var excluding = last;
            if (excluding == null)
                throw new CollectionIsEmptyException();

            if (excluding.prev != null)
            {
                this.last = excluding.prev;
                excluding.prev.next = null;
                count--;
            }
            else
            {
                this.first = this.last = null;
                count = 0;
            }

            return excluding.item;
        }


        internal void Exclude(Chain<T> excludingChain)
        {
            if (excludingChain.prev == null)
                first = excludingChain.next;
            else
                excludingChain.prev.next = excludingChain.next;

            if (excludingChain.next == null)
                last = excludingChain.prev;
            else
                excludingChain.next.prev = excludingChain.prev;

            count--;
        }


        internal void ExcludeFirst(int hashCode, System.Predicate<T> predicate,
                                   out T item, out bool found)
        {
            for (var chain = first; chain != null; chain = chain.next)
                if (chain.hashCode == hashCode && predicate(chain.item))
                {
                    item = chain.item;
                    found = true;
                    Remove(chain);
                    return;
                }

            // not found
            item = default(T);
            found = false;
        }


        internal void RemoveFirst(T item)
        {
            int theHashCode = equator.GetHashCode(item);
            Chain<T> chain = first;
            while (chain != null)
                if (chain.hashCode == theHashCode && equator.Equals(chain.item, item))
                    Remove(chain);
        }


        internal void Remove(Chain<T> chain)
        {
            if (chain.prev == null)
                first = chain.next;
            else
                chain.prev.next = chain.next;
            if (chain.next == null)
                last = chain.prev;
            else
                chain.next.prev = chain.prev;
            count--;
        }


        internal void Process(int hashCode, System.Action<T> action)
        {
            for (var chain = first; chain != null; chain = chain.next)
                if (chain.hashCode == hashCode)
                    action(chain.item);
        }


        internal void ProcessAll(System.Action<T> action)
        {
            for (var chain = first; chain != null; chain = chain.next)
                action(chain.item);
        }


        internal void ExcludeAll(Chain<T>[] chains, ref int startingIndex)
        {
            for (var chain = first; chain != null; chain = chain.next)
                chains[startingIndex++] = chain;
            count = 0;
            first = last = null;
        }


        internal void Clear()
        {
            count = 0;
            first = last = null;
        }


    }


    /// <summary>
    /// Linked list chain link.
    /// </summary>
    /// <typeparam name="T">type of linked list item.</typeparam>
    internal class Chain<T>
    {
        internal Chain<T> prev, next;
        internal T item;
        internal int hashCode;

        /// <summary>
        /// Item of the chain link.
        /// </summary>
        public T Item { get { return item; } }

        public override int GetHashCode() { return hashCode; }
        public override string ToString() { return item.ToString(); }
    }

}